package main

func main()  {
	
}

type fastNode struct {
	val int
	next *fastNode
}

func fastSort(head *fastNode) *fastNode {

	if head ==nil || head.next ==nil {
		return head
	}

	llian := &fastNode{}
	rlian := &fastNode{}
	kaililian := llian
	kairilian := rlian
	cur := head.next

	for cur != nil {
		if cur.val > head.val {
			llian.next = cur
			llian = cur
		}else {
			rlian.next = cur
			rlian = cur
		}
		cur = cur.next
	}
	llian.next = nil
	rlian.next = nil

	kaililian = fastSort(kaililian.next)
	kairilian = fastSort(kairilian.next)

	cur = kaililian
	if cur != nil {
		for cur.next != nil {
			cur = cur.next
		}
		cur.next = head
		head.next = nil  // 注意要切断原head
		if kaililian != nil {
			head.next = kaililian
		}
		return kairilian
	}
	head.next = kaililian
	return head
}

